{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Fish in a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaxFish"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #网格图中鱼的最大数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始大小为 <code>m x n</code>&nbsp;的二维整数数组&nbsp;<code>grid</code>&nbsp;，其中下标在&nbsp;<code>(r, c)</code>&nbsp;处的整数表示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果&nbsp;<code>grid[r][c] = 0</code>&nbsp;，那么它是一块 <strong>陆地</strong>&nbsp;。</li>\n",
    "\t<li>如果&nbsp;<code>grid[r][c] &gt; 0</code>&nbsp;，那么它是一块&nbsp;<strong>水域</strong>&nbsp;，且包含&nbsp;<code>grid[r][c]</code>&nbsp;条鱼。</li>\n",
    "</ul>\n",
    "\n",
    "<p>一位渔夫可以从任意 <strong>水域</strong>&nbsp;格子&nbsp;<code>(r, c)</code>&nbsp;出发，然后执行以下操作任意次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>捕捞格子&nbsp;<code>(r, c)</code>&nbsp;处所有的鱼，或者</li>\n",
    "\t<li>移动到相邻的 <strong>水域</strong>&nbsp;格子。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回渔夫最优策略下，&nbsp;<strong>最多</strong>&nbsp;可以捕捞多少条鱼。如果没有水域格子，请你返回 <code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>格子&nbsp;<code>(r, c)</code>&nbsp;<strong>相邻</strong>&nbsp;的格子为&nbsp;<code>(r, c + 1)</code>&nbsp;，<code>(r, c - 1)</code>&nbsp;，<code>(r + 1, c)</code> 和&nbsp;<code>(r - 1, c)</code>&nbsp;，前提是相邻格子在网格图内。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/03/29/example.png\" style=\"width: 241px; height: 161px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>渔夫可以从格子 <code>(1,3)</code> 出发，捕捞 3 条鱼，然后移动到格子 <code>(2,3)</code>&nbsp;，捕捞 4 条鱼。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/03/29/example2.png\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>渔夫可以从格子 (0,0) 或者 (3,3) ，捕捞 1 条鱼。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10</code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;= 10</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-fish-in-a-grid](https://leetcode.cn/problems/maximum-number-of-fish-in-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-fish-in-a-grid](https://leetcode.cn/problems/maximum-number-of-fish-in-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]', '[[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        #并查集求最大联通水域，向下，向右，无需所有\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        is_visited = set()\n",
    "        ans = 0\n",
    "        def bfs(i,j):\n",
    "            adj = [(i,j)]\n",
    "            #adj =[(x,y) for (x,y) in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1) if 0<=x<=m-1 and 0<=y<=n-1 and grid[x][y] != 0]\n",
    "            visited = set()\n",
    "            ans = 0\n",
    "            while adj :\n",
    "                queue = set()\n",
    "                for nx,ny in adj:\n",
    "                    ans += grid[nx][ny]\n",
    "                    visited.add((nx,ny))\n",
    "                    for (x, y) in [(nx + 1, ny), (nx - 1, ny), (nx, ny + 1), (nx, ny - 1)] :\n",
    "                        if 0 <= x <= m - 1 :\n",
    "                            if 0 <= y <= n - 1 :\n",
    "                                if grid[x][y] != 0 :\n",
    "                                    if (x,y) not in visited:\n",
    "                                        queue.add((x, y))\n",
    "                    #print(queue,ans)\n",
    "                adj = list(queue)\n",
    "            is_visited.update(visited)\n",
    "            return ans\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    is_visited.add((i,j))\n",
    "                    continue\n",
    "                if (i,j) not in is_visited:\n",
    "                    #queue = []\n",
    "                    ans = max(bfs(i,j),ans)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    cnt = grid[i][j]\n",
    "                    q = deque([(i, j)])\n",
    "                    grid[i][j] = 0\n",
    "                    while q:\n",
    "                        r, c = q.popleft()\n",
    "                        for x, y in (r, c + 1),(r, c - 1),(r + 1, c) ,(r - 1, c):\n",
    "                            if 0<=x<m and 0<=y<n and grid[x][y] > 0:\n",
    "                                q.append((x, y))\n",
    "                                cnt += grid[x][y]\n",
    "                                grid[x][y] = 0\n",
    "                    ans = max(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] > 0:\n",
    "                    stack.append([i, j])\n",
    "                    cur = grid[i][j]\n",
    "                    grid[i][j] = 0\n",
    "                    while stack:\n",
    "                        x, y = stack.pop()\n",
    "                        if x > 0 and grid[x - 1][y] > 0:\n",
    "                            stack.append([x - 1, y])\n",
    "                            cur += grid[x - 1][y]\n",
    "                            grid[x - 1][y] = 0\n",
    "                        if x < len(grid) - 1 and grid[x + 1][y] > 0:\n",
    "                            stack.append([x + 1, y])\n",
    "                            cur += grid[x + 1][y]\n",
    "                            grid[x + 1][y] = 0\n",
    "                        if y > 0 and grid[x][y - 1] > 0:\n",
    "                            stack.append([x, y - 1])\n",
    "                            cur += grid[x][y - 1]\n",
    "                            grid[x][y - 1] = 0\n",
    "                        if y < len(grid[0]) - 1 and grid[x][y + 1] > 0:\n",
    "                            stack.append([x, y + 1])\n",
    "                            cur += grid[x][y + 1]\n",
    "                            grid[x][y + 1] = 0\n",
    "                    ans = max(ans, cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        # 多源广搜\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        s = set(product(range(row), range(col)))\n",
    "        ans = 0\n",
    "        while s:\n",
    "            r, c = s.pop()\n",
    "            if grid[r][c]:\n",
    "                q = deque([(r, c)])\n",
    "                cnt = grid[r][c]\n",
    "                grid[r][c] = 0\n",
    "                while q:\n",
    "                    r, c = q.popleft()\n",
    "                    for r2, c2 in (r, c+1), (r, c-1), (r+1, c), (r-1, c):\n",
    "                        if -1 < r2 < row and -1 < c2 < col and grid[r2][c2]:\n",
    "                            cnt += grid[r2][c2]\n",
    "                            grid[r2][c2] = 0\n",
    "                            s.remove((r2, c2))\n",
    "                            q.append((r2, c2))\n",
    "                if cnt > ans:\n",
    "                    ans = cnt\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dir = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        \n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    res = max(res, self.fish(grid, i, j))\n",
    "        return res\n",
    "    \n",
    "    def fish(self, grid, i, j):\n",
    "        # 捕鱼\n",
    "        num = grid[i][j]\n",
    "        grid[i][j] = 0\n",
    "        for d in self.dir:\n",
    "            newi = i + d[0]\n",
    "            newj = j + d[1]\n",
    "            if newi<0 or newj<0 or newi>=len(grid) or newj>=len(grid[0]) or grid[newi][newj] == 0:\n",
    "                continue\n",
    "            num += self.fish(grid, newi, newj)\n",
    "        return num\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:\n",
    "                return 0\n",
    "            s = grid[i][j]\n",
    "            grid[i][j] = 0  # 标记成访问过\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                s += dfs(x, y)  # 四方向移动\n",
    "            return s\n",
    "        return max(max(dfs(i, j) for j in range(n)) for i in range(m))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        # 多源广搜\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        s = set(product(range(row), range(col)))\n",
    "        ans = 0\n",
    "        while s:\n",
    "            r, c = s.pop()\n",
    "            if grid[r][c]:\n",
    "                q = deque([(r, c)])\n",
    "                cnt = grid[r][c]\n",
    "                grid[r][c] = 0\n",
    "                while q:\n",
    "                    r, c = q.popleft()\n",
    "                    for r2, c2 in (r, c+1), (r, c-1), (r+1, c), (r-1, c):\n",
    "                        if -1 < r2 < row and -1 < c2 < col and grid[r2][c2]:\n",
    "                            cnt += grid[r2][c2]\n",
    "                            grid[r2][c2] = 0\n",
    "                            s.remove((r2, c2))\n",
    "                            q.append((r2, c2))\n",
    "                if cnt > ans:\n",
    "                    ans = cnt\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRE = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        # 多源广搜\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        s = set(product(range(row), range(col)))\n",
    "        ans = 0\n",
    "        while s:\n",
    "            r, c = s.pop()\n",
    "            if grid[r][c] == 0:\n",
    "                continue\n",
    "            q = deque([(r, c)])\n",
    "            cnt = grid[r][c]\n",
    "            grid[r][c] = 0\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                for dr, dc in DIRE:\n",
    "                    r2 = r + dr\n",
    "                    c2 = c + dc\n",
    "                    if -1 < r2 < row and -1 < c2 < col and grid[r2][c2] != 0:\n",
    "                        cnt += grid[r2][c2]\n",
    "                        grid[r2][c2] = 0\n",
    "                        s.remove((r2, c2))\n",
    "                        q.append((r2, c2))\n",
    "            if cnt > ans:\n",
    "                ans = cnt\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        # 多源广搜\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        s = set(product(range(row), range(col)))\n",
    "        ans = 0\n",
    "        while s:\n",
    "            r, c = s.pop()\n",
    "            if grid[r][c] == 0:\n",
    "                continue\n",
    "            q = deque([(r, c)])\n",
    "            cnt = grid[r][c]\n",
    "            grid[r][c] = 0\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                for r2, c2 in (r, c+1), (r, c-1), (r+1, c), (r-1, c):\n",
    "                    if -1 < r2 < row and -1 < c2 < col and grid[r2][c2]:\n",
    "                        cnt += grid[r2][c2]\n",
    "                        grid[r2][c2] = 0\n",
    "                        s.remove((r2, c2))\n",
    "                        q.append((r2, c2))\n",
    "            if cnt > ans:\n",
    "                ans = cnt\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self._set = defaultdict(lambda: None)\n",
    "    def find(self, x):\n",
    "        root = x\n",
    "        while self._set[root] != None:\n",
    "            root = self._set[root]\n",
    "        while x != root:\n",
    "            original_father = self._set[x]\n",
    "            self._set[x] = root\n",
    "            x = original_father\n",
    "        return root\n",
    "    def union(self, x, y):\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if rx != ry:\n",
    "            self._set[rx] = ry\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        ctr = Counter()\n",
    "        uf = UnionFind()\n",
    "        \n",
    "        M, N = len(grid), len(grid[0])\n",
    "        \n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                if grid[i][j]:\n",
    "                    if i and grid[i-1][j]:\n",
    "                        uf.union((i, j), (i-1, j))\n",
    "                    if j and grid[i][j-1]:\n",
    "                        uf.union((i, j), (i, j-1))\n",
    "        \n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                if grid[i][j]:\n",
    "                    ctr[uf.find((i, j))] += grid[i][j]\n",
    "        \n",
    "        if not ctr: return 0\n",
    "        return max(ctr.values())\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        # 多源广搜\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        s = set(product(range(row), range(col)))\n",
    "        ans = 0\n",
    "        while s:\n",
    "            r, c = s.pop()\n",
    "            if grid[r][c] == 0:\n",
    "                continue\n",
    "            q = deque([(r, c)])\n",
    "            cnt = grid[r][c]\n",
    "            grid[r][c] = 0\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                for r2, c2 in (r, c+1), (r, c-1), (r+1, c), (r-1, c):\n",
    "                    if -1 < r2 < row and -1 < c2 < col and grid[r2][c2]:\n",
    "                        cnt += grid[r2][c2]\n",
    "                        grid[r2][c2] = 0\n",
    "                        s.remove((r2, c2))\n",
    "                        q.append((r2, c2))\n",
    "            if cnt > ans:\n",
    "                ans = cnt\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(i, j):\n",
    "            ans = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                newi, newj = i + di, j + dj\n",
    "                if 0<=newi<r and 0<=newj<c and grid[newi][newj] > 0:\n",
    "                    ans += dfs(newi, newj)\n",
    "\n",
    "            return ans\n",
    "            \n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] > 0:\n",
    "                    ans = max(ans, dfs(i, j))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, g: List[List[int]]) -> int:\n",
    "        v = set()\n",
    "        m = len(g)\n",
    "        n = len(g[0])\n",
    "        def bfs(x):\n",
    "\n",
    "            if x in v:\n",
    "                return 0\n",
    "            else:\n",
    "                v.add(x)\n",
    "                ans = g[x[0]][x[1]] \n",
    "                s = [x]\n",
    "                while s:\n",
    "                    tmp = []\n",
    "                    for i, j in s:\n",
    "                        for x, y in [[0,1], [0,-1], [-1,0], [1,0]]:\n",
    "                            x += i\n",
    "                            y += j\n",
    "                            if (0<=x<m) and (0<=y<n):\n",
    "                                if (x, y) not in v:\n",
    "                                    if g[x][y]>0:\n",
    "                                        v.add((x, y))\n",
    "                                        tmp.append((x, y))\n",
    "                                        ans += g[x][y]\n",
    "                    s = tmp \n",
    "                    \n",
    "                return ans \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if g[i][j]>0:\n",
    "                    ans = max(ans, bfs((i, j)))\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        def dfs(grid,x,y):\n",
    "            if x<0 or x>=m or y<0 or y>=n or grid[x][y]==0:\n",
    "                return 0\n",
    "            s=grid[x][y]\n",
    "            grid[x][y]=0\n",
    "            s+=dfs(grid,x+1,y)\n",
    "            s+=dfs(grid,x-1,y)\n",
    "            s+=dfs(grid,x,y+1)\n",
    "            s+=dfs(grid,x,y-1)\n",
    "            return s\n",
    "        ans=0\n",
    "        for u in range(m):\n",
    "            for v in range(n):\n",
    "                ans=max(ans,dfs(grid,u,v))\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        r=0\n",
    "        def bfs(i,j):\n",
    "            if i<0 or j<0 or i>=m or j>=n or grid[i][j]==0:\n",
    "                return 0\n",
    "            tmp=grid[i][j]\n",
    "            grid[i][j]=0\n",
    "            return tmp+bfs(i+1,j)+bfs(i,j+1)+bfs(i-1,j)+bfs(i,j-1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    r=max(r,bfs(i,j))\n",
    "        return r\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        #并查集求最大联通水域，向下，向右，无需所有\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        is_visited = set()\n",
    "        ans = 0\n",
    "        def bfs(i,j):\n",
    "            adj = [(i,j)]\n",
    "            #adj =[(x,y) for (x,y) in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1) if 0<=x<=m-1 and 0<=y<=n-1 and grid[x][y] != 0]\n",
    "            visited = set()\n",
    "            ans = 0\n",
    "            while adj :\n",
    "                queue = set()\n",
    "                for nx,ny in adj:\n",
    "                    ans += grid[nx][ny]\n",
    "                    visited.add((nx,ny))\n",
    "                    for (x, y) in [(nx + 1, ny), (nx - 1, ny), (nx, ny + 1), (nx, ny - 1)] :\n",
    "                        if 0 <= x <= m - 1 and 0 <= y <= n - 1 and grid[x][y] != 0 and (x,y) not in visited:\n",
    "                            queue.add((x, y))\n",
    "                    #print(queue,ans)\n",
    "                adj = list(queue)\n",
    "            is_visited.update(visited)\n",
    "            return ans\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    is_visited.add((i,j))\n",
    "                    continue\n",
    "                if (i,j) not in is_visited:\n",
    "                    #queue = []\n",
    "                    ans = max(bfs(i,j),ans)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        direction = [(-1,0),(1,0),(0,1),(0,-1)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    q = deque([(i,j)])\n",
    "                    res = grid[i][j]\n",
    "                    grid[i][j] = 0\n",
    "                    while q:\n",
    "                        x,y = q.popleft()\n",
    "                        for dx,dy in direction:\n",
    "                            if 0 <= dx + x < m and 0 <= y + dy < n and grid[x+dx][y+dy] != 0:\n",
    "                                q.append((x+dx,y+dy))\n",
    "                                res += grid[x+dx][y+dy]\n",
    "                                grid[x+dx][y+dy] = 0\n",
    "                    ans = max(ans,res)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        steps=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        vis=[[False for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def ok(x,y):\n",
    "            if x>=0 and x<m and y>=0 and y<n:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0 and vis[i][j]==False:\n",
    "                    cnt=grid[i][j]\n",
    "                    dq=deque()\n",
    "                    dq.append((i,j))\n",
    "                    vis[i][j]=True\n",
    "                    while dq:\n",
    "                        x,y=dq.popleft()\n",
    "                        for step in steps:\n",
    "                            nx=x+step[0]\n",
    "                            ny=y+step[1]\n",
    "                            if ok(nx,ny) and grid[nx][ny]>0 and vis[nx][ny]==False:\n",
    "                                cnt+=grid[nx][ny]\n",
    "                                vis[nx][ny]=True\n",
    "                                dq.append((nx,ny))\n",
    "                    ans=max(ans,cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: list[list[int]]) -> int:\n",
    "        ans = 0\n",
    "        offset = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        que = []\n",
    "        visited = [[False] * len(grid[0]) for _ in range(len(grid))]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                que.append([i, j])\n",
    "                count = 0\n",
    "                # visited = []\n",
    "                while que:\n",
    "                    cur = que.pop(0)\n",
    "                    count += grid[cur[0]][cur[1]]\n",
    "                    visited[cur[0]][cur[1]] = True\n",
    "                    for k in offset:\n",
    "                        if 0 <= (cur[0] + k[0]) <= len(grid) - 1 and 0 <= (cur[1] + k[1]) <= len(grid[0]) - 1:\n",
    "                            if grid[cur[0] + k[0]][cur[1] + k[1]] == 0:\n",
    "                                continue\n",
    "                            if not visited[cur[0] + k[0]][cur[1] + k[1]]:\n",
    "                                if [cur[0] + k[0], cur[1] + k[1]] not in que:\n",
    "                                    que.append([cur[0] + k[0], cur[1] + k[1]])\n",
    "\n",
    "                ans = max(ans, count)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        \n",
    "        def dfs(i,j):\n",
    "            if i<0 or i>=m or j<0 or j>=n or grid[i][j]==0:\n",
    "                return 0\n",
    "\n",
    "            ans = grid[i][j]\n",
    "\n",
    "            grid[i][j] = 0 \n",
    "\n",
    "            for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:\n",
    "                ans+=dfs(x,y)\n",
    "            \n",
    "            return ans\n",
    "\n",
    "        return max(max(dfs(i, j) for j in range(n)) for i in range(m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: list[list[int]]) -> int:\n",
    "        ans=0\n",
    "        b=[[0 for i in range(len(grid[0]))]for j in range(len(grid))]\n",
    "        moves = [[0,1],[0,-1],[-1,0],[1,0]]\n",
    "        def bfs(x,y):\n",
    "            q=queue.Queue()\n",
    "            q.put((x,y))\n",
    "            b[x][y]=1\n",
    "            tot=0\n",
    "            while q.qsize()>0:\n",
    "                x1,y1=q.get()\n",
    "                tot+=grid[x1][y1]\n",
    "                for move in moves:\n",
    "                    if x1+move[0] in range(len(grid)) and y1+move[1] in range(len(grid[0])) and b[x1+move[0]][y1+move[1]]==0 and grid[x1+move[0]][y1+move[1]]!=0:\n",
    "                        q.put((x1+move[0],y1+move[1]))\n",
    "                        b[x1+move[0]][y1+move[1]]=1\n",
    "            return tot\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]!=0 and b[i][j]==0:\n",
    "                    ans = max(ans,bfs(i,j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.max = 0\n",
    "        self.father = [0] * m * n\n",
    "        self.value = [0] * m * n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k = i * n + j\n",
    "                if grid[i][j]:\n",
    "                    self.father[k] = k\n",
    "                    self.value[k] = grid[i][j]\n",
    "                    self.max = max(self.max, grid[i][j])\n",
    "                    \n",
    "    def find(self, x: int):\n",
    "        if x == self.father[x]:\n",
    "            return x\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "\n",
    "    def merge(self, i: int, j: int):\n",
    "        x, y = self.find(i), self.find(j)\n",
    "        if x != y:\n",
    "            if self.value[y] <= self.value[x]:\n",
    "                self.father[y] = x\n",
    "                self.value[x] += self.value[y]\n",
    "                self.max = max(self.max, self.value[x])\n",
    "            else:\n",
    "                self.father[x] = y\n",
    "                self.value[y] += self.value[x]\n",
    "                self.max = max(self.max, self.value[y])\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(grid)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k = i * n + j\n",
    "                if grid[i][j]:\n",
    "                    if j < n - 1 and grid[i][j+1]:\n",
    "                        uf.merge(k, k+1)\n",
    "                    if i < m - 1 and grid[i+1][j]:\n",
    "                        uf.merge(k, k+n)\n",
    "        return uf.max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = 0\n",
    "        def dfs(r, c):\n",
    "            if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0:\n",
    "                return 0\n",
    "            s = grid[r][c]\n",
    "            grid[r][c] = 0\n",
    "            return s + dfs(r-1, c) + dfs(r, c-1) + dfs(r+1, c) + dfs(r, c+1)\n",
    "            \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, dfs(i, j))\n",
    "\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        p = list(range(m * n))\n",
    "        size = sum(grid, [])\n",
    "\n",
    "        def find(x):\n",
    "            while x != p[x]:\n",
    "                p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        for i, j in product(range(m), range(n)):\n",
    "            if not grid[i][j]: continue\n",
    "            idx = find(i * n + j)\n",
    "            for di, dj in ((0, 1), (1, 0)):\n",
    "                ni, nj = i + di, j + dj\n",
    "                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj]:\n",
    "                    if idx != (idx2 := find(ni * n + nj)):\n",
    "                        p[idx2] = idx\n",
    "                        size[idx] += size[idx2]\n",
    "\n",
    "        return max(size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        def dfs(grid,x,y):\n",
    "            if x<0 or x>=m or y<0 or y>=n or grid[x][y]==0:\n",
    "                return 0\n",
    "            s=grid[x][y]\n",
    "            grid[x][y]=0\n",
    "            s+=dfs(grid,x+1,y)\n",
    "            s+=dfs(grid,x-1,y)\n",
    "            s+=dfs(grid,x,y+1)\n",
    "            s+=dfs(grid,x,y-1)\n",
    "            return s\n",
    "        ans=0\n",
    "        for u in range(m):\n",
    "            for v in range(n):\n",
    "                ans=max(ans,dfs(grid,u,v))\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:\n",
    "                return 0\n",
    "            s = grid[i][j]\n",
    "            grid[i][j] = 0  # 标记成访问过\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                s += dfs(x, y)  # 四方向移动\n",
    "            return s\n",
    "        return max(max(dfs(i, j) for j in range(n)) for i in range(m))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        def visit(i,j,grid,visited):\n",
    "            fish,fish1,fish2,fish3,fish4 = 0,0,0,0,0\n",
    "            if grid[i][j] == 0:\n",
    "                visited[i][j] = 1\n",
    "                return fish\n",
    "            visited[i][j] = 1\n",
    "            # 遍历四个方向\n",
    "            if j + 1 < n:\n",
    "                if visited[i][j+1] == 0 and grid[i][j] > 0:\n",
    "                    fish1 = visit(i,j+1,grid,visited)\n",
    "            if j - 1 >= 0:\n",
    "                if visited[i][j-1] == 0 and grid[i][j] > 0:\n",
    "                    fish2 = visit(i,j-1,grid,visited)\n",
    "            if i + 1 < m:\n",
    "                if visited[i+1][j] == 0 and grid[i][j] > 0:\n",
    "                    fish3 = visit(i+1,j,grid,visited)\n",
    "            if i - 1 >= 0:\n",
    "                if visited[i-1][j] == 0 and grid[i][j] > 0:\n",
    "                    fish4 = visit(i-1,j,grid,visited)\n",
    "            fish = fish1 + fish2 + fish3 + fish4 + grid[i][j]\n",
    "            \n",
    "            return fish\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        #  判断每个点是否访问\n",
    "        visited = []\n",
    "        for i in range(m):\n",
    "            visited.append([])\n",
    "            for j in range(n):\n",
    "                visited[i].append(0)\n",
    "        maxfish = 0\n",
    "        # 深度优先搜索\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if(visited[i][j]==0 and grid[i][j] >0):\n",
    "                    fish = visit(i,j,grid,visited)\n",
    "                    if maxfish < fish:\n",
    "                        maxfish = fish\n",
    "        return maxfish\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]\n",
    "    Sol = Solution()\n",
    "    print(Sol.findMaxFish(grid))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        is_visited = [[False] * n for _ in range(m)]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, self.dfs(is_visited, i, j, m, n, grid))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "    def dfs(self, is_visited, r, c, m, n, grid):\n",
    "        if r < 0 or r >= m or c < 0 or c >= n:\n",
    "            return 0\n",
    "        if is_visited[r][c]:\n",
    "            return 0\n",
    "        is_visited[r][c] = True\n",
    "        if grid[r][c] == 0:\n",
    "            return 0\n",
    "\n",
    "        left = self.dfs(is_visited, r, c - 1, m, n, grid)\n",
    "        right = self.dfs(is_visited, r, c + 1, m, n, grid)\n",
    "        up = self.dfs(is_visited, r - 1, c, m, n, grid)\n",
    "        down = self.dfs(is_visited, r + 1, c, m, n, grid)\n",
    "\n",
    "        return grid[r][c] + left + right + up + down"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        # 方法1、bfs\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        visited = set()\n",
    "        maxNumberOfFishes = 0\n",
    "        directions = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        dq = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                currentFishes = 0\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                if (i,j) in visited:\n",
    "                    continue\n",
    "                visited.add((i,j))\n",
    "                dq.append((i,j))\n",
    "                currentFishes += grid[i][j]\n",
    "                while dq:\n",
    "                    x_,y_ = dq.popleft()\n",
    "                    for x0,y0 in directions:\n",
    "                        x = x_ + x0\n",
    "                        y = y_ + y0\n",
    "                        if x < 0 or x >=m or y <0 or y >= n or (x,y) in visited or grid[x][y] == 0:\n",
    "                            continue\n",
    "                        dq.append((x,y))\n",
    "                        visited.add((x,y))\n",
    "                        currentFishes += grid[x][y]\n",
    "                maxNumberOfFishes = max(maxNumberOfFishes,currentFishes)\n",
    "        return maxNumberOfFishes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        p = list(range(m * n))\n",
    "        size = sum(grid, [])\n",
    "\n",
    "        def find(x):\n",
    "            while x != p[x]:\n",
    "                p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        for i, j in product(range(m), range(n)):\n",
    "            if not grid[i][j]: continue\n",
    "            idx = find(i * n + j)\n",
    "            for di, dj in ((0, 1), (1, 0), (-1, 0), (0, -1)):\n",
    "                ni, nj = i + di, j + dj\n",
    "                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj]:\n",
    "                    if idx != (idx2 := find(ni * n + nj)):\n",
    "                        p[idx2] = idx\n",
    "                        size[idx] += size[idx2]\n",
    "\n",
    "        return max(size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ans=0\n",
    "        dirctions=[(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        def dfs(x,y):\n",
    "            nonlocal res\n",
    "            grid[x][y]=0\n",
    "            for i,j in dirctions:\n",
    "                new_x,new_y=x+i,y+j\n",
    "                if 0<=new_x<m and 0<=new_y<n and grid[new_x][new_y]>0:\n",
    "                    res+=grid[new_x][new_y]\n",
    "                    dfs(new_x,new_y)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    res=grid[i][j]\n",
    "                    dfs(i,j)\n",
    "                    ans=max(ans,res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i:int,j:int):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:\n",
    "                return 0\n",
    "            s = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                s += dfs(x, y)\n",
    "            return s\n",
    "        return max(max(dfs(i, j) for j in range(n)) for i in range(m))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        # 多源广搜\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        s = set(product(range(row), range(col)))\n",
    "        ans = 0\n",
    "        while s:\n",
    "            r, c = s.pop()\n",
    "            if grid[r][c] != 0:\n",
    "                q = deque([(r, c)])\n",
    "                cnt = grid[r][c]\n",
    "                grid[r][c] = 0\n",
    "                while q:\n",
    "                    r, c = q.popleft()\n",
    "                    for r2, c2 in (r, c+1), (r, c-1), (r+1, c), (r-1, c):\n",
    "                        if -1 < r2 < row and -1 < c2 < col and grid[r2][c2] != 0:\n",
    "                            cnt += grid[r2][c2]\n",
    "                            grid[r2][c2] = 0\n",
    "                            s.remove((r2, c2))\n",
    "                            q.append((r2, c2))\n",
    "                if cnt > ans:\n",
    "                    ans = cnt\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, g: List[List[int]]) -> int:\n",
    "        m,n=len(g),len(g[0])\n",
    "        ans=0\n",
    "        def dfs(x,y):\n",
    "            ans=g[x][y]\n",
    "            g[x][y]=0\n",
    "            for i,j in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                nx,ny=x+i,y+j\n",
    "                if 0<=nx<m and 0<=ny<n and g[nx][ny]>0:\n",
    "                    ans+=dfs(nx,ny)\n",
    "            return ans\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if g[i][j]>0:\n",
    "                    ans=max(ans,dfs(i,j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not vis[i][j] and grid[i][j]:\n",
    "                    res = grid[i][j]\n",
    "                    vis[i][j] = 1\n",
    "                    q = deque([(i,j)])\n",
    "                    \n",
    "                    while q:\n",
    "                        x, y = q.popleft()\n",
    "                        for dx, dy in (x+1, y), (x-1, y), (x, y-1), (x, y+1):\n",
    "                            if 0 <= dx < m and 0 <= dy < n and grid[dx][dy] and not vis[dx][dy]:\n",
    "                                res += grid[dx][dy]\n",
    "                                vis[dx][dy] = 1\n",
    "                                q.append((dx,dy))\n",
    "                    ans = max(ans, res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: list[list[int]]) -> int:\n",
    "        ans = 0\n",
    "        offset = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        que = []\n",
    "        visited = [[False] * len(grid[0]) for _ in range(len(grid))]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                que.append([i, j])\n",
    "                count = 0\n",
    "                # visited = []\n",
    "                while que:\n",
    "                    cur = que.pop(0)\n",
    "                    count += grid[cur[0]][cur[1]]\n",
    "                    visited[cur[0]][cur[1]] = True\n",
    "                    for k in offset:\n",
    "                        if 0 <= (cur[0] + k[0]) <= len(grid) - 1 and 0 <= (cur[1] + k[1]) <= len(grid[0]) - 1:\n",
    "                            if grid[cur[0] + k[0]][cur[1] + k[1]] == 0:\n",
    "                                continue\n",
    "                            if not visited[cur[0] + k[0]][cur[1] + k[1]]:\n",
    "                                if [cur[0] + k[0], cur[1] + k[1]] not in que:\n",
    "                                    que.append([cur[0] + k[0], cur[1] + k[1]])\n",
    "\n",
    "                ans = max(ans, count)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: list[list[int]]) -> int:\n",
    "        ans = 0\n",
    "        offset = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        que = []\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                que.append([i, j])\n",
    "                count = 0\n",
    "                visited = []\n",
    "                while que:\n",
    "                    cur = que.pop(0)\n",
    "                    count += grid[cur[0]][cur[1]]\n",
    "                    visited.append([cur[0], cur[1]])\n",
    "                    for k in offset:\n",
    "                        if 0 <= (cur[0] + k[0]) <= len(grid) - 1 and 0 <= (cur[1] + k[1]) <= len(grid[0]) - 1:\n",
    "                            if grid[cur[0] + k[0]][cur[1] + k[1]] == 0:\n",
    "                                continue\n",
    "                            if [cur[0] + k[0], cur[1] + k[1]] not in visited:\n",
    "                                if [cur[0] + k[0], cur[1] + k[1]] not in que:\n",
    "                                    que.append([cur[0] + k[0], cur[1] + k[1]])\n",
    "\n",
    "                ans = max(ans, count)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i,j):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:\n",
    "                return 0\n",
    "            num = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            for x,y in [(i + 1,j),(i - 1,j),(i,j + 1),(i, j -1)]:\n",
    "                num += dfs(x,y)\n",
    "            return num\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans,dfs(i,j))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dirs=[[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        def dfs(x:int,y:int)->int:\n",
    "            res=grid[x][y]\n",
    "            grid[x][y]=0\n",
    "            for dx,dy in dirs:\n",
    "                cx,cy=x+dx,y+dy\n",
    "                if cx>=0 and cx<m and cy>=0 and cy<n and grid[cx][cy]!=0:\n",
    "                    res +=dfs(cx,cy)\n",
    "            return res\n",
    "\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]!=0:\n",
    "                    ans = max(ans,dfs(i,j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "\n",
    "        dx = [0, 1, 0, -1]\n",
    "        dy = [1, 0, -1, 0]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not vis[i][j] and grid[i][j] > 0:\n",
    "                    vis[i][j] = True\n",
    "                    q = [[i, j]]\n",
    "                    s = grid[i][j]\n",
    "                    head, tail = 0, 1\n",
    "                    while head < tail:\n",
    "                        nowx, nowy = q[head]\n",
    "                        head += 1\n",
    "                        for index in range(4):\n",
    "                            x = nowx + dx[index]\n",
    "                            y = nowy + dy[index]\n",
    "                            if x >= 0 and x < m and y >= 0 and y < n and not vis[x][y] and grid[x][y] > 0:\n",
    "                                vis[x][y] = True\n",
    "                                q.append([x, y])\n",
    "                                tail += 1\n",
    "                                s += grid[x][y]\n",
    "                    \n",
    "                    res = max(res, s)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        def getFish(grid, x, y, total):\n",
    "            if grid[x][y] == 0:\n",
    "                return total\n",
    "            else:\n",
    "                if grid[x][y] > 0:\n",
    "                    total += grid[x][y]\n",
    "                    grid[x][y] = 0\n",
    "                    if x > 0:\n",
    "                        total = getFish(grid, x - 1, y, total)\n",
    "                    if y > 0:\n",
    "                        total = getFish(grid, x, y - 1, total)\n",
    "                    if x < len(grid) - 1:\n",
    "                        total = getFish(grid, x + 1, y, total)\n",
    "                    if y < len(grid[0]) - 1:\n",
    "                        total = getFish(grid, x, y + 1, total)\n",
    "                return total\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] != 0:\n",
    "                    r = getFish(grid, i, j, 0)\n",
    "                    if r > res:\n",
    "                        res = r\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\r\n",
    "        ans = 0\r\n",
    "        m = len(grid)\r\n",
    "        n = len(grid[0])\r\n",
    "        def dfs(i,j):\r\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] <= 0:\r\n",
    "                return 0\r\n",
    "            else:\r\n",
    "                grid[i][j] = -grid[i][j]\r\n",
    "                return -grid[i][j] + dfs(i+1,j) + dfs(i-1,j) + dfs(i,j+1) + dfs(i,j-1)\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                ans = max(ans, dfs(i,j))\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        def get_ans(grid,start_x,start_y):\n",
    "            ans = 0\n",
    "            for i, j in [(0,1), (0,-1), (1,0), (-1,0)]:\n",
    "                c = start_x+i\n",
    "                r = start_y+j\n",
    "                if c<0 or c>=row or r<0 or r>=col:\n",
    "                    continue\n",
    "                else:\n",
    "                    \n",
    "                    if grid[c][r] != 0: \n",
    "                        ans += grid[c][r]\n",
    "                        grid[c][r] = 0\n",
    "                        ans += get_ans(grid,c,r)\n",
    "                    else:\n",
    "                        ans += 0\n",
    "            return ans\n",
    "\n",
    "        max_data = 0\n",
    "    \n",
    "        for start_x in range(row):\n",
    "            for start_y in range(col):\n",
    "                ans = 0\n",
    "                if grid[start_x][start_y] != 0:\n",
    "                    ans += grid[start_x][start_y]\n",
    "                    grid[start_x][start_y] = 0\n",
    "                    ans += get_ans(grid,start_x,start_y)\n",
    "                else:\n",
    "                    if ans > max_data:\n",
    "                        max_data = ans\n",
    "                        ans = 0\n",
    "                if ans > max_data:\n",
    "                    max_data = ans\n",
    "                    ans = 0\n",
    "        return max_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]!=0:\n",
    "                    res=max(res,self.dfs(i,j,grid))\n",
    "        return res\n",
    "\n",
    "    def dfs(self,i,j,grid):\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        if i<0 or i>n-1 or j<0 or j>m-1 or grid[i][j]==0:\n",
    "            return 0\n",
    "        \n",
    "        ans=grid[i][j]\n",
    "        grid[i][j]=0\n",
    "        for ni,nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "            ans+=self.dfs(ni,nj,grid)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "  def findMaxFish(self, grid):\n",
    "      \"\"\"\n",
    "      :type grid: List[List[int]]\n",
    "      :rtype: int\n",
    "      \"\"\"\n",
    "      m=len(grid)\n",
    "      n=len(grid[0])\n",
    "      had=[]   #已捕过鱼的格子\n",
    "      max_v=0  #捕鱼的最大值\n",
    "      def buyu(i,j):\n",
    "          if i<0 or i==m or j<0 or j==n:  #判断上下左右格子是否超出范围，超出则返回0\n",
    "              return 0\n",
    "          if grid[i][j]==0:    #判断当前格子是否为陆地，陆地则返回0\n",
    "              return 0\n",
    "          if [i,j] not in had:  #判断当前格子是否已捕过鱼\n",
    "              had.append([i,j]) #如果没捕过鱼，把当前坐标加入已捕过鱼列表\n",
    "              return grid[i][j]+buyu(i-1,j)+buyu(i+1,j)+buyu(i,j-1)+buyu(i,j+1)\n",
    "              #返回当前格子中捕鱼数量+(递归)上下左右格子捕鱼数量\n",
    "          else:   #如果当前格子已捕过鱼，不能重复捕鱼，返回0\n",
    "              return 0\n",
    "\n",
    "      for i in range(m):  #遍历每个格子\n",
    "          for j in range(n):\n",
    "              max_v=max(buyu(i,j),max_v)\n",
    "\n",
    "      return max_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        # 也是  最大连通块元素和\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:\n",
    "                return 0\n",
    "            \n",
    "            s = grid[i][j]\n",
    "            grid[i][j] = 0  # 标记成访问过\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 四个坐标，上下左右\n",
    "                s += dfs(x, y)  # 四方向移动\n",
    "            return s\n",
    "        return max(max(dfs(i, j) for j in range(n)) for i in range(m))\n",
    "        # return max(max(dfs(i, j) for i in range(m)) for j in range(n))  # 也可\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:\n",
    "                return 0\n",
    "            s = grid[i][j]\n",
    "            grid[i][j] = 0  # 标记成访问过\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                s += dfs(x, y)  # 四方向移动\n",
    "            return s\n",
    "        return max(max(dfs(i, j) for j in range(n)) for i in range(m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0 or i >= m or j >= n:\n",
    "                return 0\n",
    "            if grid[i][j] == 0:\n",
    "                return 0\n",
    "            ret = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            return ret + dfs(i+1, j) + dfs(i, j+1) + dfs(i-1, j) + dfs(i, j-1)\n",
    "        ret = 0\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            if grid[i][j]:\n",
    "                ret = max(ret, dfs(i, j))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        ans=cnt=0\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if i<0 or j<0 or i>=m or j>=n or grid[i][j]==0:\n",
    "                return\n",
    "            nonlocal cnt\n",
    "            cnt+=grid[i][j]\n",
    "            grid[i][j]=0\n",
    "            dfs(i-1,j)\n",
    "            dfs(i+1,j)\n",
    "            dfs(i,j-1)\n",
    "            dfs(i,j+1)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    cnt=0\n",
    "                    dfs(i, j)\n",
    "                    ans = max(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:\n",
    "                return 0\n",
    "            s = grid[i][j]\n",
    "            grid[i][j] = 0  # 标记成访问过\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                s += dfs(x, y)  # 四方向移动\n",
    "            return s\n",
    "        return max(max(dfs(i, j) for j in range(n)) for i in range(m))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        def dfs(i,j):\n",
    "            if i<0 or j<0 or i>n-1 or j>m-1 or grid[i][j]==0:\n",
    "                return 0\n",
    "            val=grid[i][j]\n",
    "            grid[i][j]=0\n",
    "            val += dfs(i-1,j)\n",
    "            val += dfs(i+1,j)\n",
    "            val += dfs(i,j-1)\n",
    "            val += dfs(i,j+1)\n",
    "            return val\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ans=max(ans,dfs(i,j))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        ans = 0\n",
    "        def dfs(i,j):\n",
    "            if i not in range(m) or j not in range(n) or grid[i][j] == 0:\n",
    "                return 0\n",
    "            tmp = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            for x,y in (i,j-1),(i,j+1),(i-1,j),(i+1,j):\n",
    "                tmp += dfs(x,y)\n",
    "            return tmp\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    ans = max(ans,dfs(i,j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ans=0\n",
    "        dirctions=[(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        def dfs(x,y):\n",
    "            nonlocal res\n",
    "            grid[x][y]=0\n",
    "            for i,j in dirctions:\n",
    "                new_x,new_y=x+i,y+j\n",
    "                if 0<=new_x<m and 0<=new_y<n and grid[new_x][new_y]>0:\n",
    "                    res+=grid[new_x][new_y]\n",
    "                    dfs(new_x,new_y)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    res=grid[i][j]\n",
    "                    dfs(i,j)\n",
    "                    ans=max(ans,res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        # 也是  最大连通块加权和\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:\n",
    "                return 0\n",
    "            \n",
    "            s = grid[i][j]\n",
    "            grid[i][j] = 0  # 标记成访问过\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 四个坐标，上下左右\n",
    "                s += dfs(x, y)  # 四方向移动\n",
    "            return s\n",
    "        return max(max(dfs(i, j) for j in range(n)) for i in range(m))\n",
    "        # return max(max(dfs(i, j) for i in range(m)) for j in range(n))  # 也可\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        # 定义深度优先搜索函数\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:\n",
    "                return 0\n",
    "            s = grid[i][j]\n",
    "            grid[i][j] = 0  # 标记此格子已经被访问\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                s += dfs(x, y)  # 递归搜索相邻的格子\n",
    "            return s\n",
    "\n",
    "        # 对每一个格子执行深度优先搜索，并返回最大的结果\n",
    "        return max(max(dfs(i, j) for j in range(n)) for i in range(m))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n,m = len(grid),len(grid[0])\n",
    "\n",
    "        ans = 0 \n",
    "        visited =[ [0]*m for _ in range(n)]\n",
    "\n",
    "        def DFS(i,j):\n",
    "            visited[i][j] = 1\n",
    "            fish = grid[i][j]\n",
    "\n",
    "            for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:\n",
    "                x,y = dx+i,dy+j \n",
    "                if 0<=x<n and 0<=y<m and visited[x][y]==0 and grid[i][j]>0:\n",
    "                    fish += DFS(x,y)\n",
    "            return fish \n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]>0:\n",
    "                    num = DFS(i,j)\n",
    "                    ans = max(ans,num)\n",
    "        \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        def dfs(x,y):\n",
    "            if x<0 or y<0 or x>=m or y>=n:\n",
    "                return 0\n",
    "            if grid[x][y]==0:\n",
    "                return 0\n",
    "            now =grid[x][y]\n",
    "            grid[x][y]=0\n",
    "            now+=dfs(x-1,y)\n",
    "            now+=dfs(x+1,y)\n",
    "            now+=dfs(x,y-1)\n",
    "            now+=dfs(x,y+1)\n",
    "            return now\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]!=0:\n",
    "                    tp=dfs(i,j)\n",
    "                    if tp>ans:\n",
    "                        ans=tp\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        # 方法2、并查集\n",
    "        class UnionFind:\n",
    "            # 初始化\n",
    "            def __init__(self, n):\n",
    "                self.size = [0] * n\n",
    "                self.parent = [0] * n\n",
    "                self.fish = [0] * n\n",
    "                for i in range(n):\n",
    "                    self.parent[i] = i\n",
    "\n",
    "            # 合并两个节点（注意：这里有个路径优化的体现呢！！！）\n",
    "            def Union(self, p, q):\n",
    "                pRoot, qRoot = self.find(p), self.find(q)\n",
    "                if pRoot == qRoot:\n",
    "                    return\n",
    "                # 平衡优化\n",
    "                if pRoot != qRoot:\n",
    "                    if self.size[pRoot] > self.size[qRoot]:\n",
    "                        self.parent[qRoot] = pRoot\n",
    "                        self.fish[pRoot] += self.fish[qRoot]\n",
    "                    elif self.size[pRoot] < self.size[qRoot]:\n",
    "                        self.parent[pRoot] = qRoot\n",
    "                        self.fish[qRoot] += self.fish[pRoot]\n",
    "                    else:\n",
    "                        self.parent[qRoot] = pRoot\n",
    "                        self.size[pRoot] += 1\n",
    "                        self.fish[pRoot] += self.fish[qRoot]\n",
    "\n",
    "            # 查找父节点\n",
    "            def find(self, x):\n",
    "                if x != self.parent[x]:\n",
    "                    x = self.find(self.parent[x])\n",
    "                return self.parent[x]\n",
    "            \n",
    "            # 初始化鱼池中鱼的数量\n",
    "            def initFish(self,x,num):\n",
    "                self.fish[x] = num \n",
    "\n",
    "            # 返回连通分量中鱼的最大数量\n",
    "            def getMaxFish(self):\n",
    "                maxFish = 0\n",
    "                for f in self.fish:\n",
    "                    maxFish = max(maxFish,f)\n",
    "                return maxFish\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    uf.initFish(i * n + j,grid[i][j])\n",
    "                x1 = i * n + j\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    if i > 0 and grid[i-1][j] > 0:\n",
    "                        uf.Union(i * n + j,(i - 1) * n + j)\n",
    "                    if j > 0 and grid[i][j-1] > 0:\n",
    "                        uf.Union(i * n + j,i * n + j - 1)\n",
    "        return uf.getMaxFish()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        visited = [ [0 for i in range(len(grid[0])) ] for j in grid ]\n",
    "        def get_fish( row , col , lake , visited ):\n",
    "            fish = lake[row][col]\n",
    "            visited[row][col] = 1\n",
    "            for next_r,next_c in [ (row+1,col) , (row-1,col) , (row,col+1), (row,col-1) ]:\n",
    "                if next_r >= len(lake) or next_r < 0 or next_c >= len(grid[0]) or next_c <0 :  #考虑边际\n",
    "                    continue\n",
    "                if lake[next_r][next_c] != 0 and visited[next_r][next_c] != 1:  #这块地方没有钓过鱼\n",
    "                    fish += get_fish( next_r, next_c , lake , visited )\n",
    "            return fish\n",
    "        res = 0 \n",
    "        for i in range( len(grid) ):\n",
    "            for j in range( len(grid[0] )):\n",
    "                if grid[i][j] != 0 and visited[i][j] !=1:\n",
    "                    tmp_fish = get_fish( i , j , grid, visited)\n",
    "                    res = max(tmp_fish , res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        vis=[[False for i in range(n)] for i in range(m)]\n",
    "        def dfs(x,y):\n",
    "            s=grid[x][y]\n",
    "            vis[x][y]=True\n",
    "            for i,j in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:\n",
    "                if 0<=i<m and 0<=j<n and grid[i][j]!=0 and not vis[i][j] :\n",
    "                    s+=dfs(i,j)\n",
    "            return s\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]!=0 and not vis[i][j]:\n",
    "                    ans=max(ans,dfs(i,j))\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:\n",
    "                return 0\n",
    "            \n",
    "            s = grid[i][j]\n",
    "            grid[i][j] = 0  # 标记成访问过\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 四个坐标，上下左右\n",
    "                s += dfs(x, y)  # 四方向移动\n",
    "            return s\n",
    "        return max(max(dfs(i, j) for j in range(n)) for i in range(m))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        fa = list(range(m * n))\n",
    "        sz = [0] * (m * n)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v:\n",
    "                    sz[i * n + j] = v\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            x, y = find(x), find(y)\n",
    "            if x == y: return\n",
    "            fa[x] = y\n",
    "            sz[y] += sz[x]\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v:\n",
    "                    for r, c in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                        if 0 <= r < m and 0 <= c < n and grid[r][c]:\n",
    "                            union(i * n + j, r * n + c)\n",
    "\n",
    "        return max(sz)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxFish(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        mx=0\n",
    "        print(m,n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    stack=[[i,j]]\n",
    "                    cnt=grid[i][j]\n",
    "                    grid[i][j]=0\n",
    "                    while stack:\n",
    "                        x,y=stack.pop()\n",
    "                        for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                            if 0<=x1<m and 0<=y1<n:\n",
    "                                if grid[x1][y1]>0:\n",
    "                                    stack.append([x1,y1])\n",
    "                                    cnt+=grid[x1][y1]\n",
    "                                    grid[x1][y1]=0\n",
    "\n",
    "                    mx=max(cnt,mx)\n",
    "        print(grid)\n",
    "        return mx\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
